package com.hit.basmath.interview.we_meet.bytedance.news;

/**
 * 题目：环节点的走法数
 * <p>
 * 题目描述：
 * <p>
 * 一个环上有10个点,编号为0-9,从0点出发,每步可以顺时针到下一个点,也可以逆时针到上一个点,求:经过n步又回到0点有多少种不同的走法？
 * <p>
 * 举例：
 * 如果n=1，则从0出发只能到1或者9，不可能回到0，共0种走法
 * 如果n=2，则从0出发有4条路径:0->1->2, 0->1->0, 0->9->8, 0->9->0,其中有两条回到了0点，故一共有2种走法
 * <p>
 * 动态规划：
 * 状态方程为：d(k, j) = d(k-1, j-1) + d(k-1, j+1);
 * 由于可能发生越界，故转换为
 * d(k, j) = d(k-1, (j-1+n)%n) + d(k-1, (j+1)%n);
 * 解释为：j步达到i点的问题，转化为j-1步从相邻的两个节点到达目标节点的方法数之和。
 */
public class CircleStep {
    // n 为环数，k 为步数
    public int GetSteps(int n, int k) {
        if (n == 0) return 1;
        // 如果只有2个环，则偶数有1个方法，奇数不能到达
        if (n == 2) {
            if (k % 2 == 0) {
                return 1;
            } else {
                return 0;
            }
        }

        int[][] dp = new int[k + 1][n];
        // 0步到达0点有1种方法
        dp[0][0] = 1;
        // 0步到达任意点有0种方法,可java自赋0值，可省略
        //for(int i=0;i<n;i++){
        //    dp[0][i]=0
        //}
        for (int j = 1; j <= k; j++) {
            for (int i = 0; i < n; i++) {
                //j步达到i点的问题，转化为j-1步从相邻的两个节点到达目标节点的方法数之和。
                //需要保证在0~n-1范围，故需要防止越界进行处理
                dp[j][i] = dp[j - 1][(i - 1 + n) % n] + dp[j - 1][(i + 1) % n];
            }
        }
        //这里的0对应的是回到0点，达到任意点可以通过将0改为目标点即可
        return dp[k][0];
    }

    public static void main(String[] args) {
        System.out.println(new CircleStep().GetSteps(10, 2));
    }
}
